import { Compare, defaultCompare } from "../../utils/compare.js";
import BinaryTreeNode from "./BinaryTreeNode.js";

export default class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.root = null;
    this.compareFn = compareFn; // 自定义比较函数
  }

  /**
   * 插入节点操作
   * @param {BinaryTreeNode} node 节点
   * @param {*} value
   * @returns {BinaryTreeNode}
   */
  insertNode(node, value) {
    if (node == null) {
      return new BinaryTreeNode(value);
    }
    // 如果小了，继续向左树遍历
    if (this.compareFn(value, node.value) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, value);
    }
    // 如果大了，继续向右树遍历
    if (this.compareFn(value, node.value) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, value);
    }
    // 最终返回node，此时如果插入的值已经存在，则不进行任何操作
    return node;
  }

  /**
   * 向二叉查找树中插入值
   * @param {*} value 需要插入的值
   */
  insert(value) {
    this.root = this.insertNode(this.root, value);
    return this;
  }

  /**
   * 中序遍历的方法遍历二叉搜索树的节点
   * @param {BinaryTreeNode} node 需要遍历的节点
   * @param {function} callback 回调函数支持一个参数：value
   */
  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.value);
      this.inOrderTraverseNode(node.right, callback);
    }
  }

  /**
   * 中序遍历的方法遍历二叉搜索树，
   * 将以从小到大顺序访问所有节点
   * @param {function} callback 回调函数支持一个参数：value
   */
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

  /**
   * 先序遍历的方法遍历二叉搜索树的节点
   * @param {BinaryTreeNode} node 需要遍历的节点
   * @param {function} callback 回调函数支持一个参数：value
   */
  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node.value);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }

  /**
   * 先序遍历的方法遍历二叉搜索树，
   * 先访问节点本身，再访问左侧，然后访问右侧
   * @param {function} callback 回调函数支持一个参数：value
   */
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  /**
   * 后序遍历的方法遍历二叉搜索树的节点
   * @param {BinaryTreeNode} node 需要遍历的节点
   * @param {function} callback 回调函数支持一个参数：value
   */
  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.value);
    }
  }

  /**
   * 后序遍历的方法遍历二叉搜索树，
   * 先访问节点的子节点，再访问节点本身
   * @param {function} callback 回调函数支持一个参数：value
   */
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  /**
   * 查找最左边的节点，就是最小值
   * @param {BinaryTreeNode} node 需要遍历的节点
   * @returns {BinaryTreeNode}
   */
  minNode(node) {
    let currentNode = node;
    while (currentNode != null && currentNode.left != null) {
      currentNode = currentNode.left;
    }
    return currentNode;
  }

  /**
   * 查找最小值
   * @returns {*|null}
   */
  min() {
    if (this.root == null) {
      return null;
    }
    return this.minNode(this.root).value;
  }

  /**
   * 查找最右边的节点，就是最大值
   * @param {BinaryTreeNode} node 需要遍历的节点
   * @returns {BinaryTreeNode}
   */
  maxNode(node) {
    let currentNode = node;
    while (currentNode != null && currentNode.right != null) {
      currentNode = currentNode.right;
    }
    return currentNode;
  }

  /**
   * 查找最大值
   * @returns {*|null}
   */
  max() {
    if (this.root == null) {
      return null;
    }
    return this.maxNode(this.root).value;
  }

  /**
   * 查询节点中是否存在value值
   * @param {BinaryTreeNode} node 需要查询的节点
   * @param {*} value
   * @returns {boolean}
   */
  searchNode(node, value) {
    if (node == null) {
      return false;
    }

    if (this.compareFn(value, node.value) === Compare.LESS_THAN) {
      // 如果小了，查询左节点
      return this.searchNode(node.left, value);
    } else if (this.compareFn(value, node.value) === Compare.BIGGER_THAN) {
      // 如果大了，查询右节点
      return this.searchNode(node.right, value);
    } else {
      return true;
    }
  }

  /**
   * 查询二叉搜索树种是否存在value值
   * @param {*} value
   * @returns {boolean}
   */
  search(value) {
    return this.searchNode(this.root, value);
  }

  /**
   * 删除节点操作
   * @param {BinaryTreeNode} node 需要查询的节点
   * @param {*} value 需要删除的值
   * @returns {BinaryTreeNode}
   */
  removeNode(node, value) {
    // 当node不存在时返回null
    if (node == null) {
      return null;
    }

    // 如果值比当前节点小，则进入左侧树继续查找
    if (this.compareFn(value, node.value) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, value);
      return node;
    }

    // 如果值比当前节点大，则进入右侧树继续查找
    if (this.compareFn(value, node.value) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, value);
      return node;
    }

    // 当上面的条件都不满足，说明已经找到需要删除的节点
    // 当节点没有子节点时，直接删除该节点
    if (node.left == null && node.right == null) {
      node = null;
      return node;
    }

    // 当节点左侧为null时，将其右侧子树移上来
    if (node.left == null) {
      node = node.right;
      return node;
    }

    // 当节点右侧为null时，将其左侧子树移上来
    if (node.right == null) {
      node = node.right;
      return node;
    }

    // 当该节点有左右子节点时，需要查找其右侧子树中的最小值，将其值赋值给该节点，并删除右侧子树的最小节点
    const aux = this.minNode(node.right);
    node.value = aux.value;
    node.right = this.removeNode(node.right, aux.value);
    return node;
  }

  /**
   * 从树中移除value值
   * @param {*} value 需要移除的值
   */
  remove(value) {
    this.root = this.removeNode(this.root, value);
  }
}
